/*
 * Copyright (c) 2019 Wormpex.com. All Rights Reserved.
 */

package com.sk.leetcode.arithmetic;

/**
 * @author ke.su date: 2019-06-20 Time: 下午7:15
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * <p>
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 * 示例:
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 */

public class Test84 {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        int max = largestRectangleArea(heights);
        System.out.println(max);
    }


    public static int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int max = 0;

        for (int i = 0; i < length; i++) {
            int kuan = 1;

            int numLeft = i, numRight = i;
            while (numLeft > 0 || numRight < length - 1) {
                if(numLeft > 0) {
                    if(heights[i] < heights[--numLeft]) {
                        kuan++;
                    } else {
                        numLeft = 0;
                    }
                }
                if(numRight < length - 1) {
                    if(heights[i] <= heights[++numRight]) {
                        kuan++;
                    } else {
                        numRight = length;
                    }
                }
            }
            int res = kuan * heights[i];
            if(res > max) {
                max = res;
            }

        }

        return max;
    }
}
